#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
	
};
class Solution12
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        ListNode* phead = new ListNode, * pre, * cur, * next, * nnext;
        phead->next = head;
        pre = phead;
        cur = pre->next;
        while (cur && cur->next)
        {
            next = cur->next;
            nnext = next->next;
            pre->next = next;
            next->next = cur;
            cur->next = nnext;
            pre = cur;
            if (pre->next)
                cur = pre->next;
            else
                cur = nullptr;
        }
        return phead->next;
    }
};
class Solution
{
public:
    void reorderList(ListNode* head)
    {
        int shift = 1;
        ListNode* pre, * tail, * newhead = new ListNode, * newtail = newhead;
        while (head)
        {
            if (shift == 1)
            {
                ListNode* tmp = head->next;
                newtail->next = head;
                newtail = newtail->next;
                head->next = nullptr;
                head = tmp;
                shift = 0;
            }
            else
            {
                pre = head;
                tail = pre->next;
                while (tail&&tail->next)
                {
                    pre = tail;
                    tail = tail->next;
                }
                if (tail == nullptr)
                    newtail->next = pre;
                else
                    newtail->next = tail;
                newtail = newtail->next;
                pre->next = nullptr;
                shift = 1;
            }
        }

    }
};
int main()
{
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    Solution().reorderList(n1);
    return 0;
}